시간, 공간 복잡도

공간 복잡도

프로그램을 실행 및 완료하는 데 필요한 저장공간의 양을 의미한다.
특정한 크기의 입력에 대해 알고리즘의 메모리 사용량을 분석하는 것.

예시

1. n! 구하기
   • 재귀 함수로 구현하므로 변수 n 에 따라 함수가 n 번 호출된다.
   • 공간 복잡도는 $O(n)$
2. 배열에서 n 인덱스 전까지 합 구하기
   • 사용되는 변수는 배열, n, result, i 이다. 배열은 n 보다 큰 공간을 할당해야 하기 때문에 $O(n)$
3. n! 반복문으로 구하기
   • 반복문을 통해서 구현할 때 변수 하나에 값을 모두 저장하기 때문에 공간 복잡도는 $O(1)$

시간 복잡도

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간.